// 方法一思路分析：

// 首先从头到尾遍历整个字符串；
// 当遇到字符"("则入栈，遇到字符")"则出栈；
// 出栈时，如果栈已经为空，则返回 false；
// 当字符串遍历完毕以后，判断栈是否为空。

// 方式一：栈
const Stack = require("./Stack");
function isPairing1(str = "") {
  const stack = new Stack();

  for (let i of str) {
    if (i === "(") {
      stack.push(i);
    } else if (i === ")") {
      if (stack.isEmpty()) {
        return false;
      } else {
        stack.pop();
      }
    }
  }

  return stack.size() === 0;
}

// 方法二思路分析：

// 声明变量 num 为 0，并从头到尾遍历整个字符串；
// 当遇到字符"("则 num 加 1，遇到字符")"num 减 1；
// 在遍历的过程中，当 num 减 1 时，num 的值已经为 0 则返回 false；
// 当字符串遍历完毕以后，判断 num 是否为 0。

// 方式二：计数

function isPairing2(str = "") {
  let num = 0;

  for (let i of str) {
    if (i === "(") {
      num++;
    } else if (i === ")") {
      if (num === 0) {
        return false;
      } else {
        num--;
      }
    }
  }

  return num === 0;
}

let str = "(abin))";
console.log(isPairing1(str));
console.log(isPairing2(str));

// 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
// 用一个 map 来维护左括号和右括号的对应关系
/**
 * 左括号必须用相同类型的右括号闭合。
   左括号必须以正确的顺序闭合。
   注意空字符串可被认为是有效字符串。
 */
const leftToRight = {
  "(": ")",
  "[": "]",
  "{": "}",
};

const isValid = function (s) {
  // 结合题意，空字符串无条件判断为 true
  if (!s) {
    return true;
  }
  // 初始化 stack 数组
  const stack = [];
  // 缓存字符串长度
  const len = s.length;
  // 遍历字符串
  for (let i = 0; i < len; i++) {
    // 缓存单个字符
    const ch = s[i];
    // 判断是否是左括号，这里我为了实现加速，没有用数组的 includes 方法，直接手写判断逻辑
    if (ch === "(" || ch === "{" || ch === "[") stack.push(leftToRight[ch]);
    // 若不是左括号，则必须是和栈顶的左括号相配对的右括号
    else {
      // 若栈不为空，且栈顶的左括号没有和当前字符匹配上，那么判为无效
      if (!stack.length || stack.pop() !== ch) {
        return false;
      }
    }
  }
  // 若所有的括号都能配对成功，那么最后栈应该是空的
  return !stack.length;
};
console.log(isValid('{[]{[}}'));